/*
题目描述：机器人从格子的(0,0)开始移动，不能进入行坐标和列坐标的数位之和大于k的格子。求该机器人能够达到多少个格子？
方法：回溯法，二维平面内机器人的移动
 */
public class E13 {
    public static void main(String[] args){
        int threshold = 18;
        int rows = 38;
        int cols = 38;
        int res = movingCount(threshold, rows, cols);
        System.out.println(res);
    }

    public static int movingCount(int threshold, int rows, int cols){
        if(threshold < 0 || rows <= 0 || cols <= 0){
            return 0;
        }
        Boolean[] visited = new Boolean[rows * cols];
        for(int i = 0; i < rows * cols; i++){
            visited[i] = false;
        }

        int count = movingCountCore(threshold, rows, cols, 0,0,visited);

        return count;
    }

    public static int movingCountCore(int threshold, int rows, int cols, int row, int col, Boolean[] visited){
        int count = 0;
        if(check(threshold, rows, cols, row, col, visited)){
            visited[row * cols + col] = true;

            count = 1 + movingCountCore(threshold, rows, cols, row - 1, col, visited)
                    + movingCountCore(threshold, rows, cols, row, col - 1, visited)
                    + movingCountCore(threshold, rows, cols, row + 1, col, visited)
                    + movingCountCore(threshold, rows, cols, row, col + 1, visited);
        }
        return count;
    }
    //检查是否可以进入该格子
    public static boolean check(int threshold, int rows, int cols, int row, int col, Boolean[] visited){
        if(row >= 0 && row < rows && col >= 0 && col < cols && getDigitSum(row) + getDigitSum(col) <= threshold && !visited[row * cols + col]){
            return true;
        }
        return false;
    }
    //计算数位之和
    public static int getDigitSum(int number){
        int sum = 0;
        while(number > 0){
            sum += number % 10;
            number /= 10;
        }
        return sum;
    }
}
/*
1388
 */